// Time:  O(n^4)
// Space: O(n^2)

#include <vector>
using namespace std;

class Solution {
public:
    int largestOverlap(vector<vector<int>>& img1, vector<vector<int>>& img2) {
        vector<int> count(pow(2 * img1.size() - 1, 2));
        for (int i = 0; i < img1.size(); ++i) {
            for (int j = 0; j < img1[i].size(); ++j) {
                if  (!img1[i][j]) {
                    continue;
                }
                for (int m = 0; m < img2.size(); ++m) {
                   for (int n = 0; n < img2[m].size(); ++n) {
                        if (!img2[m][n]) {
                            continue;
                        }
                        ++count[(img1.size() - 1 + i - m) * (2 * img1.size() - 1) +
                                 img1.size() - 1 + j - n];
                   }
                }
            }
        }
        return *max_element(count.cbegin(), count.cend());
    }
};
